class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n=s.length();
        unordered_set<string> rem;
        for(int i=0;i<wordDict.size();i++){
            rem.insert(wordDict[i]);
        }
        vector<bool> jud(n+1,false);
        jud[0]=true;
        for(int i=1;i<=n;i++){
            for(int j=0;j<i;j++){
                if(jud[j]&&rem.find(s.substr(j,i-j))!=rem.end()){
                    jud[i]=true;
                    break;
                }
            }
        }
        return jud[n];
    }
};
